package test2;

import test2.ListNode;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

public class Demo1 {
    public static void main(String[] args) {
        ListNode head = ListUnit.createList(new int[]{1,1});
        System.out.println(chkPalindrome(head));
    }
    public static boolean chkPalindrome(ListNode A) {
        if(A == null || A.next == null) {
            return true;
        }
        ListNode slow = A, fast = A, prev = A;
        while(fast != null && fast.next != null) {
            prev = slow;
            slow = slow.next;
            fast = fast.next.next;
        }
        ListNode cur = slow, next = slow.next;
        while(cur != null) {
            cur.next = prev;
            prev = cur;
            cur = next;
            if(cur != null) {
                next = cur.next;
            }
        }
        ListNode left = A, right = prev;
        while(left != right && right.next != left) {
            if(left.val != right.val) {
                return false;
            }
            left = left.next;
            right = right.next;
        }
        return true;
    }

    public static void main1(String[] args) {
        int[] arr = {};
        ListNode head = ListUnit.createList(arr);
        ListNode partition = partition(head, 0);
        while (partition != null) {
            System.out.print(partition.val + " ");
            partition = partition.next;
        }
    }
    public static ListNode partition(ListNode pHead, int x) {
        ListNode smallHead = new ListNode(0), smallCur = smallHead;
        ListNode bigHead = new ListNode(0), bigCur = bigHead;
        ListNode cur = pHead;
        while(cur != null) {
            if(cur.val < x) {
                smallCur.next = cur;
                smallCur = smallCur.next;
            } else {
                bigCur.next = cur;
                bigCur = bigCur.next;
            }
            cur = cur.next;
        }
        smallCur.next = bigHead.next;
        return smallHead.next;
    }
}
